<!DOCTYPE html>
<html>
<head><meta name="generator" content="Hexo 3.8.0">
  <meta charset="utf-8">
  

  
  <title>Hexo</title>
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
  <meta name="description" content="树状数组可直接从基本原理开始看。 从图形学算法说起Median Filter概述Median Filter 在现代的图形处理中是非常基础并且广泛应用的算法 (翻译叫 中值滤波器，为了不让人一看到就觉得是高深的东西，还是选择了使用它的英文名，更加能让人明白是个什么东西) ，如下图，基本就能猜到这是一个什么样的算法了，可以简单的认为是PS中的”模糊”那个操作。 r pixel-Median Filte">
<meta property="og:type" content="article">
<meta property="og:title" content="Hexo">
<meta property="og:url" content="http://yoursite.com/2018/12/08/树状数组/index.html">
<meta property="og:site_name" content="Hexo">
<meta property="og:description" content="树状数组可直接从基本原理开始看。 从图形学算法说起Median Filter概述Median Filter 在现代的图形处理中是非常基础并且广泛应用的算法 (翻译叫 中值滤波器，为了不让人一看到就觉得是高深的东西，还是选择了使用它的英文名，更加能让人明白是个什么东西) ，如下图，基本就能猜到这是一个什么样的算法了，可以简单的认为是PS中的”模糊”那个操作。 r pixel-Median Filte">
<meta property="og:locale" content="default">
<meta property="og:image" content="http://yoursite.com/2018/12/08/树状数组/_v_images/20181207160858181_22773.webp%20=560x">
<meta property="og:image" content="http://yoursite.com/2018/12/08/树状数组/_v_images/20181207160953871_14729.webp">
<meta property="og:image" content="http://yoursite.com/2018/12/08/树状数组/_v_images/20181206125403591_17361.webp">
<meta property="og:image" content="http://yoursite.com/2018/12/08/树状数组/_v_images/20181206133758662_31464.webp">
<meta property="og:image" content="http://yoursite.com/2018/12/08/树状数组/_v_images/20181207163850707_18534.webp">
<meta property="og:image" content="http://yoursite.com/2018/12/08/树状数组/_v_images/20181207162506178_26778.webp">
<meta property="og:image" content="http://yoursite.com/2018/12/08/树状数组/_v_images/20181207164326688_13174.webp">
<meta property="og:image" content="http://yoursite.com/2018/12/08/树状数组/_v_images/20181207164743628_27672.webp">
<meta property="og:updated_time" content="2018-12-07T08:49:22.874Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="Hexo">
<meta name="twitter:description" content="树状数组可直接从基本原理开始看。 从图形学算法说起Median Filter概述Median Filter 在现代的图形处理中是非常基础并且广泛应用的算法 (翻译叫 中值滤波器，为了不让人一看到就觉得是高深的东西，还是选择了使用它的英文名，更加能让人明白是个什么东西) ，如下图，基本就能猜到这是一个什么样的算法了，可以简单的认为是PS中的”模糊”那个操作。 r pixel-Median Filte">
<meta name="twitter:image" content="http://yoursite.com/2018/12/08/树状数组/_v_images/20181207160858181_22773.webp%20=560x">
  
    <link rel="alternate" href="/atom.xml" title="Hexo" type="application/atom+xml">
  
  
    <link rel="icon" href="/favicon.png">
  
  
    <link href="//fonts.googleapis.com/css?family=Source+Code+Pro" rel="stylesheet" type="text/css">
  
  <link rel="stylesheet" href="/css/style.css">
</head>
</html>
<body>
  <div id="container">
    <div id="wrap">
      <header id="header">
  <div id="banner"></div>
  <div id="header-outer" class="outer">
    <div id="header-title" class="inner">
      <h1 id="logo-wrap">
        <a href="/" id="logo">Hexo</a>
      </h1>
      
    </div>
    <div id="header-inner" class="inner">
      <nav id="main-nav">
        <a id="main-nav-toggle" class="nav-icon"></a>
        
          <a class="main-nav-link" href="/">Home</a>
        
          <a class="main-nav-link" href="/archives">Archives</a>
        
      </nav>
      <nav id="sub-nav">
        
          <a id="nav-rss-link" class="nav-icon" href="/atom.xml" title="RSS Feed"></a>
        
        <a id="nav-search-btn" class="nav-icon" title="Search"></a>
      </nav>
      <div id="search-form-wrap">
        <form action="//google.com/search" method="get" accept-charset="UTF-8" class="search-form"><input type="search" name="q" class="search-form-input" placeholder="Search"><button type="submit" class="search-form-submit">&#xF002;</button><input type="hidden" name="sitesearch" value="http://yoursite.com"></form>
      </div>
    </div>
  </div>
</header>
      <div class="outer">
        <section id="main"><article id="post-树状数组" class="article article-type-post" itemscope="" itemprop="blogPost">
  <div class="article-meta">
    <a href="/2018/12/08/树状数组/" class="article-date">
  <time datetime="2018-12-08T03:04:37.708Z" itemprop="datePublished">2018-12-08</time>
</a>
    
  </div>
  <div class="article-inner">
    
    
    <div class="article-entry" itemprop="articleBody">
      
        <h1 id="树状数组"><a href="#树状数组" class="headerlink" title="树状数组"></a>树状数组</h1><p>可直接从基本原理开始看。</p>
<h2 id="从图形学算法说起"><a href="#从图形学算法说起" class="headerlink" title="从图形学算法说起"></a>从图形学算法说起</h2><h3 id="Median-Filter概述"><a href="#Median-Filter概述" class="headerlink" title="Median Filter概述"></a>Median Filter概述</h3><p>Median Filter 在现代的图形处理中是非常基础并且广泛应用的算法 (翻译叫 中值滤波器，为了不让人一看到就觉得是高深的东西，还是选择了使用它的英文名，更加能让人明白是个什么东西) ，如下图，基本就能猜到这是一个什么样的算法了，可以简单的认为是PS中的”模糊”那个操作。<br><img src="_v_images/20181207160858181_22773.webp =560x" alt="MedianFilter"></p>
<h3 id="r-pixel-Median-Filter算法"><a href="#r-pixel-Median-Filter算法" class="headerlink" title="r pixel-Median Filter算法"></a>r pixel-Median Filter算法</h3><p>首先对于一张宽为W，高为H的图片，每个像素点存了一个颜色值，这里为了把问题简化，先讨论黑白图片，黑白图片的每个像素值可以认为是一个[0, 255]的整数（如图一-1-2，为了图片看起来不是那么的密密麻麻，像素值的范围取了[0, 10]）。<br>r pixel-Median Filter 算法描述如下：<br>对于每个第i行第j列的像素点p(i, j)，像四周扩展一个宽和高均为(2r + 1)的矩形区域，将矩形区域内的像素值按非降序排列后，用排在最中间的那个数字取代原来的像素点p(i, j)的值( 边界的那圈不作考虑 )，下文会将排在最中间的那个数字称为这个序列的中位数。<br><img src="_v_images/20181207160953871_14729.webp" alt="pixel-medianfilter"><br> 如图，r = 1，红框代表(2, 3) (下标从0计数，行优先)这个像素点所选取的2r + 1的矩形区域，将内中数字进行非降序排列后，得到[0 1 1 2 3 4 6 7 9]，所以(2, 3)这个像素点的值将从 6 变成 3。<br>这样就可以粗略得到一个时间复杂度为O(n^4logn )的算法（枚举每个像素点，对于每个像素点取矩形窗口元素排序后取中值）。n代表了图片的尺寸，也就是当图片越大，这个算法的执行效率就越低，而且增长迅速。那么如何将这个算法进行优化呢？如果对于二维的情况不是很容易下手的话，不妨先从一维的情况进行考虑。</p>
<h3 id="一维模型"><a href="#一维模型" class="headerlink" title="一维模型"></a>一维模型</h3><p>将问题转化成一维，可以描述成：给定n(n &lt;= 100000)个范围在[0, 255]的数字序列a[i] (1 &lt;= i &lt; = n)和一个值r (2r+1 &lt;= n)，对于所有的a[k] (r+1 &lt;= k &lt;= n-r)，将它变成 a[k-r … k+r] 中的中位数。<br>   a[1…7] = [1 7 6 4 3 2 1]   r = 2<br>   d[3] = median( [1 7 6 4 3] ) = 4<br>   d[4] = median( [7 6 4 3 2] ) = 4<br>   d[5] = median( [6 4 3 2 1] ) = 3<br>所以原数组就会变成a[1..7] = [1 7 4 4 3 2 1]</p>
<p>那么总共需要计算的元素为n-2r，取这些元素的左右r个元素的值需要2r+1次操作，(n-2r)*(2r+1) 当r = (n-1)/4 时取得最大值，为 (n+1)^2 / 4，再加上排序的时间复杂度，所以最坏情况的时间复杂度为O( n^2 logn )。n的范围不允许这么高复杂度的算法，尝试进行优化。<br>考虑第i个元素的2r+1区域a[ i-r … i+r ]和第i+1个元素的2r+1区域a[ i+1-r … i+1+r ]，后者比前者少了一个元素a[i-r]，多了一个元素a[i+1+r]，其它元素都是一样的，那么在计算第i+1个元素的情况时如何利用第i个元素的情况就成了问题的关键。</p>
<h3 id="数据结构的设计"><a href="#数据结构的设计" class="headerlink" title="数据结构的设计"></a>数据结构的设计</h3><p>我们现在假设有这样一种数据结构，可以支持以下三种操作：<br>      1、插入(Insert)，将一个数字插入到该数据结构中；<br>      2、删除(Delete), 将某个数字从该数据结构中删除；<br>      3、询问(Query), 询问该数据结构中存在数字的中位数；<br>如果这三个操作都能在O( log(n) )或者O(1)的时间内完成，那么这个问题就可以完美解决了。具体做法是：<br>首先将a[1…2r+1]这些元素都插入到该数据结构中，然后询问中位数替换掉a[r+1]，再删除a[1]，插入a[2r+2]，询问中位数替换掉a[r+2]，以此类推，直到计算完第n-r个元素。所有操作都在O( log(n) ) 时间内完成的话，总的时间复杂度就是O( nlogn )。<br>我们来看什么样的数据结构可以满足这三条操作都在O( log(n) )的时间内完成，考虑每个数字的范围是[0, 255]，如果我们将这些数字映射到一个线性表中(即 HASH表)，插入和删除操作都可以做到O(1)。<br>用一个辅助数组d[256]，插入a[i]执行的是d[ a[i] ] ++，删除a[i]执行的是 d[ a[i] ] –；询问操作是对d数组进行顺序统计，顺序枚举i，找到第一个满足sum{d[j] | 1 &lt;= j &lt;= i} &gt;= r+1的 i 就是所求中位数，这样就得到了一个时间复杂度为O(Kn)的算法，其中K是数字的值域（这里讨论的问题值域是256）。<br>相比之前的算法，这种方法已经前进了一大步，至少n的指数下降了大于一个数量级，但是也带来了一个问题，如果数字的值域很大，复杂度还是会很大，所以需要更好的算法支持。</p>
<h3 id="树状数组华丽登场"><a href="#树状数组华丽登场" class="headerlink" title="树状数组华丽登场"></a>树状数组华丽登场</h3><p>这里引入一种数据结构 - 树状数组 ( Binary Indexed Tree，BIT，二分索引树 )，它只有两种基本操作，并且都是操作线性表的数据的：<br>      1、add( i, 1 )      (1&lt;=i&lt;=n)                       对第i个元素的值自增1           O(logn)<br>      2、sum( i )         (1&lt;=i&lt;=n)                       统计[1…i]元素值的和             O(logn)<br>      试想一下，如果用HASH来实现这两个函数，那么1的复杂度是O(1)，而2的复杂度就是O(n)了，而树状数组实现的这两个函数可以让两者的复杂度都达到O(logn)。<br>有了这两种操作，我们需要将它们转化成之前设计的数据结构的那三种操作，首先：<br>      1、插入(Insert)，对应的是 add(i, 1)，时间复杂度O( logn )<br>      2、删除(Delete), 对应的是 add(i, -1), 时间复杂度O( logn )<br>      3、询问(Query), 由于sum( i )能够统计[1…i]元素值的和，换言之，它能够得到我们之前插入的数据中小于等于i的数的个数，那么如果能够知道sum(i) &gt;= r + 1的最小的i，那这个i就是所有插入数据的中位数了（因为根据上文的条件，插入的数据时刻保证有2r+1个）。因为sum(i)是关于 i 的递增函数，所以基于单调性我们可以二分枚举i (1 &lt;= i &lt;= n)，得到最小的 i 满足sum(i) &gt;= r + 1，每次的询问复杂度就是 O( logn <em> logn )。 一个logn是二分枚举的复杂度，另一个logn是sum函数的复杂度。<br>这样一来，一维的Median Filter模型的整体时间复杂度就降到了O(n </em> logn * logn)，已经是比较高效的算法了。<br>接下来就是要来说说树状数组的具体实现了。</p>
<h2 id="基本原理"><a href="#基本原理" class="headerlink" title="基本原理"></a>基本原理</h2><p>树状数组或者二叉索引树也称作Binary Indexed Tree，又叫做Fenwick树；它的查询和修改的时间复杂度都是log(n)，空间复杂度则为O(n)，这是因为树状数组通过将线性结构转化成树状结构，从而进行跳跃式扫描。通常使用在高效的计算数列的前缀和，区间和。<br><img src="_v_images/20181206125403591_17361.webp" alt="树状数组图示"><br>其中a数组就是原数组，c数组则是树状数组，可以发现：<br>C1 = A1<br>C2 = A1+A2<br>C3 = A3<br>C4 = A1+A2+A3+A4<br>C5 = A5<br>C6 = A5+A6<br>C7 = A7<br>C8 = A1+A2+A3+A4+A5+A6+A7+A8<br>C7 = A9</p>
<p>建议直接看C8，因为它最具代表性。<br>我们从中可以发现，其实Ci还有一种更加普适的定义，它表示的其实是一段原数组A的连续区间和。根据定义，右区间是很明显的，一定是i，即Ci表示的区间的最后一个元素一定是Ai，那么接下来就是要求Ci表示的第一个元素是什么。从图上可以很容易的清楚，其实就是顺着Ci的最左儿子一直找直到找到叶子结点，那个叶子结点就是Ci表示区间的第一个元素。<br>      更加具体的，如果i的二进制表示为 ABCDE1000，那么它最左边的儿子就是 ABCDE0100，这一步是通过结点父子关系的定义进行逆推得到，并且这条路径可以表示如下：<br>      ABCDE1000 =&gt; ABCDE0100 =&gt; ABCDE0010 =&gt; ABCDE0001<br>      这时候，ABCDE0001已经是叶子结点了，所以它就是Ci能够表示的第一个元素的下标，那么我们发现，如果用k来表示i的二进制末尾0的个数，Ci能够表示的A数组的区间的元素个数为2^k，又因为区间和的最后一个数一定是Ai，所以有如下公式：<br>      Ci  =  sum{ A[j] |  i - 2^k + 1 &lt;= j &lt;= i }    （帮助理解：将j的两个端点相减+1 等于2^k）</p>
<h3 id="lowbit"><a href="#lowbit" class="headerlink" title="lowbit"></a>lowbit</h3><p>树状数组lowbit()函数所求的就是最低位1的位置所以可以通过位运算来计算。<br>树状数组通过 x&amp;(x^(x-1)) 能够成功求出lowbit的原因：<br>首先设x=6，即$110_{(2)}$ 于是我们使 x-1=101 可以发现，当我们将一个二进制数减一时，从最低位一（即lowbit）开始向后的部分与之前全部相反，因为减去的1对后面的每一位都有影响，同时因为是二进制，影响就是让每一位都取反了。<br>110–&gt;101<br>从最低位一（第二位）开始向后全部相反了 所以我们再与 x 异或一发，那么从lowbit开始往后全是1。<br>110^101=011<br>然后我们再用x与新数按位与一下 因为 x lowbit 以前的部分是1或0，lowbit 是1，之后的部分都是0，新数 lowbit 之前的部分都是0，lowbit 是1，之后的部分都是1 所以与完之后他们的交集就是 lowbit<br>110&amp;011=010<br>而 lowbit 的常用计算方法是 x&amp;-x ，其原理与上面的方法不尽相同 这个式子运用了计算机的补码计算原理 补码计算简单来讲就是原码的反码反加一 如：<br>$0110_{(2)}=6$<br>变为反码后为 0001<br>再加一为 $0010_{(2)}$ 即它的补码</p>
<p>可以发现变为反码后 x 与反码数字位每一位都不同， 所以当反码加1后神奇的事情发生了，反码会逢1一直进位直到遇到0，且这个0变成了1，所以这个数最后面出现了一个 100… 串。 由于是反码，进位之后由于1的作用使进位的部分全部取反及与原码相同，所以可以发现 lowbit 以前的部分 x 与其补码即 -x 相反， lowbit x 与 -x 都是1，lowbit 以后 x 与 -x 都是0 所以 x&amp;-x 后除了 lowbit 位是1，其余位都是0。<br>计算负数补码的过程：留下所有最右边的0和最右边第一个1，其余位取反。<br><strong>注意：LOWBIT无法处理0的情况，因为它的结果也是0，那么最终就是一个死循环</strong></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">lowbit</span><span class="params">(<span class="keyword">int</span> x)</span></span>&#123;</span><br><span class="line">	<span class="keyword">return</span> x&amp;(-x);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="单点修改"><a href="#单点修改" class="headerlink" title="单点修改"></a>单点修改</h3><p>当我们要对最底层的值进行更新时，那么它相应的父亲节点存储的和也需要进行更新。<br>注意x+lowbit(x)可以求出x的父亲节点。<br>比如要对A6进行修改，则要修改C6、C8。（8是由6+lowbit(6)计算得来）</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">add</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> v)</span></span>&#123;</span><br><span class="line">	<span class="keyword">while</span>(x&lt;=n)&#123;</span><br><span class="line">		a[x]+=v;</span><br><span class="line">		x+=lowbit(x);</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="区间查询"><a href="#区间查询" class="headerlink" title="区间查询"></a>区间查询</h3><p>而查询的时候，则需要向前进行统计。<br>比如要查询A1+A2+…+A5，则只需计算C5+C4。（4是由5-lowbit(5)计算得来）<br>此处查询的是前缀和，利用前缀和也容易计算任意区间和。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">sum</span><span class="params">(<span class="keyword">int</span> x)</span></span>&#123;</span><br><span class="line">	<span class="keyword">int</span> ans=<span class="number">0</span>;</span><br><span class="line">	<span class="keyword">while</span>(x&gt;<span class="number">0</span>)&#123;</span><br><span class="line">		ans+=a[x];</span><br><span class="line">		x-=lowbit(x);</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> ans;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="测试"><a href="#测试" class="headerlink" title="测试"></a>测试</h2><p>利用基本原理已经可以实现一些基础的树状数组的功能了。一般来说，树状数组所实现的功能，线段树也都能实现。<br>但树状数组代码量小，实现简单且容易扩展到高纬度。<br>以下是简单的测试代码：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;bits\stdc++.h&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> N=<span class="number">100005</span>;</span><br><span class="line"><span class="keyword">int</span> n,a[N];</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">lowbit</span><span class="params">(<span class="keyword">int</span> x)</span></span>&#123;</span><br><span class="line">	<span class="keyword">return</span> x&amp;(-x);</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">add</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> v)</span></span>&#123;</span><br><span class="line">	<span class="keyword">while</span>(x&lt;=n)&#123;</span><br><span class="line">		a[x]+=v;</span><br><span class="line">		x+=lowbit(x);</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">sum</span><span class="params">(<span class="keyword">int</span> x)</span></span>&#123;</span><br><span class="line">	<span class="keyword">int</span> ans=<span class="number">0</span>;</span><br><span class="line">	<span class="keyword">while</span>(x&gt;<span class="number">0</span>)&#123;</span><br><span class="line">		ans+=a[x];</span><br><span class="line">		x-=lowbit(x);</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> ans;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">	<span class="built_in">cin</span>&gt;&gt;n;</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++)&#123;</span><br><span class="line">		<span class="keyword">int</span> x;</span><br><span class="line">		<span class="built_in">cin</span>&gt;&gt;x;</span><br><span class="line">		add(i,x);</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++)</span><br><span class="line">		<span class="built_in">printf</span>(<span class="string">"sum(%d)=%d\n"</span>,i,sum(i));</span><br><span class="line">	<span class="built_in">printf</span>(<span class="string">"add(1,-1)\n"</span>);add(<span class="number">1</span>,<span class="number">-1</span>);</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++)</span><br><span class="line">		<span class="built_in">printf</span>(<span class="string">"sum(%d)=%d\n"</span>,i,sum(i));</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="进阶原理"><a href="#进阶原理" class="headerlink" title="进阶原理"></a>进阶原理</h2><h3 id="前缀和与差分"><a href="#前缀和与差分" class="headerlink" title="前缀和与差分"></a>前缀和与差分</h3><p>前缀和：其实可以把它理解为数学上的数列的前n项和（对于一个一维数组的前缀和）。<br>我们定义对于一个数组a的前缀和数组s，s[i] = a[1]+a[2]+…+a[i]。<br>二维前缀和：与一维前缀和类似，设s[i][j]表示所有a[i’][j’]的和。（1≤i’≤i,1≤j’≤j）<br>有一点像“矩形的面积”那样，把一整块区域的值都加起来。<br>前缀和的用途：一般用来求区间和。<br>对于一维情况，现在我给出一个数列a，要求你回答m次询问，每次询问下标j到k的和。朴素的做法显然是对于每次询问都执行一次相加操作，然后输出结果。这样做是正确的，但是当m过大时就会导致计算次数过多而有可能超时。<br>超时的原因一目了然，重复计算。那么我们应该怎么改进这个方法呢？想象一下，我们如果先提前算好了每一个位置的前缀和，然后用s[k]-s[j]，结果不就是我们这次询问的答案吗？这样便会使计算量大大减小。<br>对于二维的区间和，也是类似的。<br><img src="_v_images/20181206133758662_31464.webp" alt="二维前缀和图示"><br>我们借助这个图片研究一下。假设在这个矩阵（二维数组）中，我们要求和的是上图中红色区域。现在我们已经预处理出了所有点的前缀和，现在给定两个点（x1,y1），（x2,y2），我们要求以这两个点连线为对角线的一个子矩阵的数值之和。我们重点考虑用前缀和的快速做法。<br>首先我们可以把s[x2][y2]求出来，它代表整个大矩形的前缀和，然后我们分别减去它左边多出来的一块的前缀和和下边多出来一块的前缀和，可以发现，在我们剪掉这两个多出的区域时，下边的一小块被减了两次，但减两次显然是不合理的，我们应该加回来。<br>所以对于一次的查询答案ans应该等于s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]。<br>这个二维前缀和也称差分序列。<br><strong>用差分实现区间操作</strong><br>给定一个长度为n的数列a，要求支持操作add(L,R,k)表示对a[L]~a[R]的每个数都加上k。并求修改后的序列a。<br>我们考虑用差分的做法。这里需要一个辅助数组c，c[i]=a[i]-a[i-1]。即a数组是c数组的前缀和。我们对[L,R]区间进行加k操作，只需<strong>在c[L]处加一个k，在c[R+1]处就减去一个k</strong>。最后求序列的每个位置变成了多少，只需要求一下c数组的前缀和就好。<br>对于二维的情况，一个n*m的矩阵，要求支持操作add(x1,y1,x2,y2,a)，表示对于以(x1,y1)为左下角，(x2,y2)为右上角的矩形区域，每个元素都加上a。要求修改后的矩阵。<br>我们的做法和一维类似。用数组c存储差量。c[i][j]=a[i][j]-a[i][j-1]-a[i-1][j]+a[i-1][j-1]。<strong>在c[x1][y1]处加上a，在c[x2+1][y1]和c[x1][y2+1]处减a，在c[x2+1][y2+1]再加上a</strong>。最后(i,j)位置上的数值就是c数组在(i,j)位置的前缀和。</p>
<p>我们对[L,R]区间进行加value操作，在C[L]处加上value，在C[R+1]处减去value，因为最后要用c数组的前缀和与原始数组分别相加，所以在C[L]处加上value只对L以后数有影响，在L以后的前缀和都加上了value，因为要求的作用范围是[L,R]，所以R以后的前缀和不能产生影响，则应该在C[R+1]处减去value，以与前面加的value相抵消。二维数组同理。</p>
<h3 id="区间修改-单点查询"><a href="#区间修改-单点查询" class="headerlink" title="区间修改+单点查询"></a>区间修改+单点查询</h3><p>这里用的是差分的思想。<br>我们设原数组为a，则我们需要维护一个差分数组d： d[i]=a[i]-a[i-1]<br>那么我们可以得到： $a[i]=\sum_{j=1}^id[j]$<br>现在a[i]被表达成了一个数组内连续的几个元素的和，这样我们就解决了查询的问题，那么我们该如何修改呢？<br>当我们需要将区间[l,r]上的每个数都加上x时，因为d数组是个差分数组，所以我们可以直接在树状数组上将d[l]加上x，d[r+1]减去x即可，测试代码如下：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;bits\stdc++.h&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> N=<span class="number">100005</span>;</span><br><span class="line"><span class="keyword">int</span> n,a[N],d[N];</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">lowbit</span><span class="params">(<span class="keyword">int</span> x)</span></span>&#123;</span><br><span class="line">	<span class="keyword">return</span> x&amp;(-x);</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">add</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> v)</span></span>&#123;</span><br><span class="line">	<span class="keyword">while</span>(x&lt;=n)&#123;</span><br><span class="line">		d[x]+=v;</span><br><span class="line">		x+=lowbit(x);</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">query</span><span class="params">(<span class="keyword">int</span> x)</span></span>&#123;</span><br><span class="line">	<span class="keyword">int</span> ans=<span class="number">0</span>;</span><br><span class="line">	<span class="keyword">while</span>(x&gt;<span class="number">0</span>)&#123;</span><br><span class="line">		ans+=d[x];</span><br><span class="line">		x-=lowbit(x);</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> ans;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">	<span class="built_in">cin</span>&gt;&gt;n;</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++)&#123;</span><br><span class="line">		<span class="built_in">cin</span>&gt;&gt;a[i];</span><br><span class="line">		add(i,a[i]-a[i<span class="number">-1</span>]);</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="built_in">printf</span>(<span class="string">"for i=1~3,add 6\n"</span>);</span><br><span class="line">	add(<span class="number">1</span>,<span class="number">6</span>);add(<span class="number">4</span>,<span class="number">-6</span>);</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++)&#123;</span><br><span class="line">		<span class="built_in">printf</span>(<span class="string">"a[%d]=%d\n"</span>,i,query(i));</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="built_in">printf</span>(<span class="string">"for i=2~4,add -5\n"</span>);</span><br><span class="line">	add(<span class="number">2</span>,<span class="number">-5</span>);add(<span class="number">5</span>,<span class="number">5</span>);</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++)&#123;</span><br><span class="line">		<span class="built_in">printf</span>(<span class="string">"a[%d]=%d\n"</span>,i,query(i));</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="区间修改-区间查询"><a href="#区间修改-区间查询" class="headerlink" title="区间修改+区间查询"></a>区间修改+区间查询</h3><p>我们还是需要引入d数组，那么当我们需要将区间[l,r]上的每个数都加上x时，我们还是可以直接在树状数组上将d[l]加上x，d[r+1]减去x。那么问题来了，如何查询区间[l,r]的和？<br>考虑前缀和s[i]=$\sum_{j=1}^ia[j]$，根据d数组的定义，可以进一步推得：</p>
<p>$$<br>s[i]=\sum_{j=1}^id[j]<em>(i-j+1)\<br>s[i]=(i+1)</em>\sum_{j=1}^id[j]-\sum_{j=1}^ij<em>d[j]<br>$$<br>注意，此处的d数组与网上许多博客中的d数组不一样，网上的d数组多为增量数组，即d[i]表示a[i]需要增加的量。<br>而此处的d数组为差分数组，d的前缀和就是a。因此在s[i]里不需要再加上a[i]。<br>这样我们就不难看sum[i]是由哪三个部分组成的了。我们需要用一个s数组维护a数组的前缀和，d1与d2两个树状数组，d1维护d数组，d2维护d[i]</em>i，测试代码如下：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;bits\stdc++.h&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> N=<span class="number">100005</span>;</span><br><span class="line"><span class="keyword">int</span> n,a[N],d1[N],d2[N];</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">lowbit</span><span class="params">(<span class="keyword">int</span> x)</span></span>&#123;</span><br><span class="line">	<span class="keyword">return</span> x&amp;(-x);</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">add</span><span class="params">(<span class="keyword">int</span> *arr,<span class="keyword">int</span> x,<span class="keyword">int</span> v)</span></span>&#123;</span><br><span class="line">	<span class="keyword">while</span>(x&lt;=n)&#123;</span><br><span class="line">		arr[x]+=v;</span><br><span class="line">		x+=lowbit(x);</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">modify</span><span class="params">(<span class="keyword">int</span> l,<span class="keyword">int</span> r,<span class="keyword">int</span> v)</span></span>&#123;</span><br><span class="line">	add(d1,l,v);add(d1,r+<span class="number">1</span>,-v);</span><br><span class="line">	add(d2,l,l*v);add(d2,r+<span class="number">1</span>,-(r+<span class="number">1</span>)*v);</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">sum</span><span class="params">(<span class="keyword">int</span> *arr,<span class="keyword">int</span> x)</span></span>&#123;</span><br><span class="line">	<span class="keyword">int</span> ans=<span class="number">0</span>;</span><br><span class="line">	<span class="keyword">while</span>(x&gt;<span class="number">0</span>)&#123;</span><br><span class="line">		ans+=arr[x];</span><br><span class="line">		x-=lowbit(x);</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> ans;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">getsum</span><span class="params">(<span class="keyword">int</span> x)</span></span>&#123;</span><br><span class="line">	<span class="keyword">return</span> (x+<span class="number">1</span>)*sum(d1,x)-sum(d2,x);</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">	freopen(<span class="string">"input.txt"</span>,<span class="string">"r"</span>,<span class="built_in">stdin</span>);</span><br><span class="line">	<span class="built_in">cin</span>&gt;&gt;n;</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++)&#123;</span><br><span class="line">		<span class="built_in">cin</span>&gt;&gt;a[i];</span><br><span class="line">		add(d1,i,a[i]-a[i<span class="number">-1</span>]);</span><br><span class="line">		add(d2,i,i*(a[i]-a[i<span class="number">-1</span>]));</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="built_in">printf</span>(<span class="string">"for i=3~6,add 3\n"</span>);</span><br><span class="line">	modify(<span class="number">3</span>,<span class="number">6</span>,<span class="number">3</span>);</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++)&#123;</span><br><span class="line">		<span class="built_in">printf</span>(<span class="string">"a[%d]=%d\n"</span>,i,getsum(i)-getsum(i<span class="number">-1</span>));</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="经典模型"><a href="#经典模型" class="headerlink" title="经典模型"></a>经典模型</h2><h3 id="PUIQ模型"><a href="#PUIQ模型" class="headerlink" title="PUIQ模型"></a>PUIQ模型</h3><p>一个长度为n(n &lt;= 500000)的元素序列，一开始都为0，现给出三种操作：</p>
<pre><code>1. add x v :    给第x个元素的值加上v；     (  a[x] += v )
2. sub x v :    给第x个元素的值减去v；     (  a[x] -= v )
3. sum x y：  询问第x到第y个元素的和；  ( print sum{ a[i] | x &lt;= i &lt;= y } )
</code></pre><p>这是树状数组最基础的模型，1和2的操作就是对应的单点更新，3的操作就对应了成端求和。<br>具体得，1和2只要分别调用add(x, v)和add(x, -v), 而3则是输出sum(y) - sum(x-1)的值。<br>我把这类问题叫做<strong>PUIQ模型(Point Update Interval Query 点更新，段求和)</strong>。</p>
<h3 id="IUPQ模型"><a href="#IUPQ模型" class="headerlink" title="IUPQ模型"></a>IUPQ模型</h3><p>一个长度为n(n &lt;= 500000)的元素序列，一开始都为0，现给出两种操作：</p>
<pre><code>1. add x y v :    给第x个元素到第y个元素的值都加上v；     (  a[i] += v, 其中 x &lt;= i &lt;= y )
2. get x：         询问第x个元素的值；                               (  print  a[x] )
</code></pre><p>这类问题对树状数组稍微进行了一个转化，但是还是可以用add和sum这两个函数来解决，对于操作1我们只需要执行两个操作，即add(x, v)和add(y+1, -v)；而操作2则是输出sum(x)的值。<br>这样就把区间更新转化成了单点更新，单点求值转化成了区间求和。<br>我把这类问题叫做<strong>IUPQ模型(Interval Update Point Query 段更新，点求值)</strong>。</p>
<h3 id="逆序模型"><a href="#逆序模型" class="headerlink" title="逆序模型"></a>逆序模型</h3><h4 id="简要原理"><a href="#简要原理" class="headerlink" title="简要原理"></a>简要原理</h4><p>给定一个长度为n(n &lt;= 500000)的排列a[i]，求它的逆序对对数。1 5 2 4 3 的逆序对为(5,2)(5,3)(5,4)(4,3)，所以答案为4。<br>朴素算法，枚举任意两个数，判断他们的大小关系进行统计，时间复杂度O(n^2)。</p>
<p>来看一个给定n个元素的排列 X0 X1 X2 … Xn-2 Xn-1,对于某个 Xi 元素，如果想知道以它为”首”的逆序对的对数( 形如(XiXj) 的逆序对)，就是需要知道 Xi+1 … Xn-2 Xn-1 这个子序列中小于 Xi 的元素的个数。</p>
<p>那么我们只需要对这个排列从后往前枚举，每次枚举到 Xi 元素时，执行cnt += sum(Xi-1)，然后再执行add(Xi, 1)，n个元素枚举完毕，得到的cnt值就是我们要求的逆序数了。总的时间复杂度O(nlogn)。</p>
<p>这个模型和之前的区别在于它不是将原数组的下标作为树状数组的下标，而是将元素本身作为树状数组的下标。逆序模型作为树状数组的一个经典思想有着非常广泛的应用。</p>
<h4 id="详细解释"><a href="#详细解释" class="headerlink" title="详细解释"></a>详细解释</h4><h5 id="什么是逆序数？"><a href="#什么是逆序数？" class="headerlink" title="什么是逆序数？"></a>什么是逆序数？</h5><p>在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序数的总数就是这个排列的逆序数。</p>
<h5 id="用树状数组求逆序数的总数"><a href="#用树状数组求逆序数的总数" class="headerlink" title="用树状数组求逆序数的总数"></a>用树状数组求逆序数的总数</h5><h6 id="该背景下树状数组的含义："><a href="#该背景下树状数组的含义：" class="headerlink" title="该背景下树状数组的含义："></a>该背景下树状数组的含义：</h6><p>我们假设一个数组A[n],当A[n]=0时表示数字n在序列中没有出现过，A[n]=1表示数字n在序列中出现过。A对应的树状数组为c[n],则c[n]对应维护的是数组A[n]的内容，即树状数组c可用于求A中某个区间的值的和。</p>
<p>树状数组的插入函数(假设为 void insert(int i,int x) )的含义：在求逆序数这个问题中，我们的插入函数通常使用为insert( i , 1 )，即将数组A[i]的值加1 (A数组开始应该初始化为0，所以也可以理解为设置A[ i ]的值为1，即将数字i 加入到序列的意思 )。，同时维护c数组的值。</p>
<p>树状数组中区间求和函数(假设函数定义为： int getsun(int i ) )的含义：该函数的作用是用于求序列中小于等于数字 i 的元素的个数。这个是显而易见的，因为树状数组c 维护的是数组A的值，则该求和函数即是用于求下标小于等于 i 的数组A的和，而数组A中元素的值要么是0要么是1，所以最后求出来的就是小于等于i的元素的个数。</p>
<p>所以要求序列中比元素a大的数的个数，可以用i - getsum(a)即可( i 表示此时序列中元素的个数)。</p>
<h6 id="如何使用树状数组求逆序数总数"><a href="#如何使用树状数组求逆序数总数" class="headerlink" title="如何使用树状数组求逆序数总数"></a>如何使用树状数组求逆序数总数</h6><p>首先来看如何减小问题的规模:<br>要想求一个序列 a b c d,的逆序数的个数，可以理解为先求出a b c的逆序数的个数k1，再在这个序列后面增加一个数d，求d之前的那个序列中值小于d的元素的个数k2，则k1+k2即为序列a b c d的逆序数的个数。</p>
<p>举个例子加以说明：<br>假设给定的序列为 4 3 2 1，我们从左往右依次将给定的序列输入，每次输入一个数temp时，就将当前序列中大于temp的元素的个数计算出来，并累加到ans中，最后ans就是这个序列的逆序数个数。<br><img src="_v_images/20181207163850707_18534.webp" alt="数组数组求逆序对"><br>当所有的元素都插入到序列后，即可得到序列{4 3 2 1}的逆序数的个数为1+2+3=6。</p>
<h6 id="代码实现"><a href="#代码实现" class="headerlink" title="代码实现"></a>代码实现</h6><figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;string&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> N 1010</span></span><br><span class="line"><span class="keyword">int</span> c[N]; </span><br><span class="line"><span class="keyword">int</span> n;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">lowbit</span><span class="params">(<span class="keyword">int</span> i)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">return</span> i&amp;(-i);</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">insert</span><span class="params">(<span class="keyword">int</span> i,<span class="keyword">int</span> x)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">while</span>(i&lt;=n)&#123;</span><br><span class="line">        c[i]+=x;</span><br><span class="line">        i+=lowbit(i);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">getsum</span><span class="params">(<span class="keyword">int</span> i)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> sum=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">while</span>(i&gt;<span class="number">0</span>)&#123;</span><br><span class="line">        sum+=c[i];</span><br><span class="line">        i-=lowbit(i);</span><br><span class="line">    &#125; </span><br><span class="line">    <span class="keyword">return</span> sum;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">output</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++) <span class="built_in">cout</span>&lt;&lt;c[i]&lt;&lt;<span class="string">" "</span>;</span><br><span class="line">    <span class="built_in">cout</span>&lt;&lt;<span class="built_in">endl</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">while</span>(<span class="built_in">cin</span>&gt;&gt;n)&#123;</span><br><span class="line">        <span class="keyword">int</span> ans=<span class="number">0</span>;</span><br><span class="line">        <span class="built_in">memset</span>(c,<span class="number">0</span>,<span class="keyword">sizeof</span>(c));</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++)&#123;</span><br><span class="line">            <span class="keyword">int</span> a;</span><br><span class="line">            <span class="built_in">cin</span>&gt;&gt;a;</span><br><span class="line">            insert(a,<span class="number">1</span>);</span><br><span class="line">            ans+=i-insert(a);<span class="comment">//统计当前序列中大于a的元素的个数</span></span><br><span class="line">        &#125;</span><br><span class="line">        <span class="built_in">cout</span>&lt;&lt;ans&lt;&lt;<span class="built_in">endl</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h4 id="例题"><a href="#例题" class="headerlink" title="例题"></a>例题</h4><p>给定N(N &lt;= 100000)个区间，定义两个区间(Si, Ei)和(Sj, Ej)的’&gt;’如下：如果Si &lt;= Sj and Ej &lt;= Ei and Ei - Si &gt; Ej - Sj,则 (Si, Ei) &gt; (Sj, Ej)，现在要求每个区间有多少区间’&gt;’它。<br>将上述三个关系式化简，可以得到 区间i &gt; 区间j 的条件是：区间i 完全覆盖 区间j，并且两者不相等。<br><img src="_v_images/20181207162506178_26778.webp" alt="树状数组逆序模型"><br>对区间进行排序，排序规则为：左端点递增，如果左端点相同，则右端点递减。<br>然后枚举区间，不断插入区间右端点，因为区间左端点是保持递增的，所以对于某个区间(Si, Ei)，只需要查询树状数组中[Ei, MAX]这一段有多少已经插入的数据，就能知道有多少个区间是比它大的，这里需要注意的是多个区间相等的情况，因为有排序，所以它们在排序后的数组中一定是相邻的，所以在遇到有相等区间的情况，需要”延迟”插入。等下一个不相等区间出现时才把之前保存下来的区间右端点进行插入。插入完毕再进行统计。<br>这里的插入即add(Ej, 1)，统计则是sum(MAX) - sum(Ei - 1)  (其中j &lt; i)。</p>
<h3 id="二分模型"><a href="#二分模型" class="headerlink" title="二分模型"></a>二分模型</h3><p>给定N(N &lt;= 100000)个编号为1-N的球，将它们乱序丢入一个“神奇的容器”中，作者会在丢的同时询问其中编号第K大的那个球，“神奇的容器”都能够从容作答，并且将那个球给吐出来，然后下次又可以继续往里丟。<br>       现在要你来模拟这个神奇的容器的功能。可以抽象成两种操作：</p>
<pre><code>1. put x                 向容器中放入一个编号为x的球；
2. query K             询问容器中第K大的那个球，并且将那个球从容器中去除（保证K&lt;容器中球的总数）；
</code></pre><p>这个问题其实就是一维Median Filter的原型了，只是那个问题的K = r+1，而这里的K是用户输入的一个常量。所谓<strong>二分模型就是在求和的过程中，利用求和函数的单调性进行二分枚举。</strong><br>对于操作1，只是单纯地执行add(x, 1)即可；而对于操作2，我们要看第K大的数满足什么性质，由于这里的数字不会有重复，所以一个显而易见的性质就是一定有K-1个数大于它，假设它的值为x，那么必然满足下面的等式：sum(N) - sum( x ) == K-1，然而，满足这个等式的x可能并不止一个，来看下面的图：<br><img src="_v_images/20181207164326688_13174.webp" alt="树状数组二分模型"><br>图中灰色的格子表示容器中的球，分别为2、3、7、8，然后我们需要求第3大的球，理论的球编号为3，但是满足上面等式的球的编号为3、4、5、6。所以我们需要再加一个限制条件，即满足上面等式的最小的x。于是我们二分枚举x，当满足sum(N) - sum( x ) &lt;= K-1时，将右区间缩小（说明找的数x偏大，继续往小的找），否则左区间增大(说明找的数x偏小，继续往大的找)，直到找到满足条件的最小的x为止。单次操作的时间复杂度为O( logn * logn )。</p>
<h2 id="二维树状数组"><a href="#二维树状数组" class="headerlink" title="二维树状数组"></a>二维树状数组</h2><h3 id="再说Median-Filter"><a href="#再说Median-Filter" class="headerlink" title="再说Median Filter"></a>再说Median Filter</h3><p>基于二分模型的一维Median Filter问题已经圆满解决了，那么最后让我们回到二维的Median Filter问题上来。<br><img src="_v_images/20181207164743628_27672.webp" alt="二维medianfilter"><br>有了一维的基础，对于二维的情况，其实也是一样的，如图三-5-1，图中红色的框为(1, 1)这个像素点的(2r+1)矩形区域，橙色的框则是(1, 2)的，它们的差别其实只是差了两列；同样的，橙色框和黄色框也差了两列，于是，我们可以从左向右枚举，每次将这个矩形框向右推进一格，然后将”离开”框的那一列数据从树状数组中删除，将”进入”框的那一列数据插入到树状数组中，然后统计中位数。<br>当枚举到右边界时，将矩形框向下推进一格，然后迂回向左，同样按照之前的方案统计中位数，就这样呈蛇字型迂回前进（具体顺序如图所示的红、橙、黄、绿、青、蓝、紫），这样就得到了一个O( n3lognlogn )的算法，比朴素算法下降了一个数量级。</p>
<h3 id="多维树状数组模型"><a href="#多维树状数组模型" class="headerlink" title="多维树状数组模型"></a>多维树状数组模型</h3><p>给定一个N*N(N &lt;= 1000)的矩形区域，执行两种操作：</p>
<pre><code>1. add x y v                                     在(x, y)加上一个值v；
2. sum x1 y1 x2 y2                          统计矩形(x1, y1) - (x2, y2)中的值的和；
</code></pre><p>PUIQ模型的二维版本。我们设计两种基本操作：</p>
<pre><code>1. add(x, y, v)        在(x, y)这个格子加上一个值v；
2. sum(x, y)           求矩形区域(1, 1) - (x, y)内的值的和，那么(x1,y1)-(x2,y2)区域内的和可以通过四个求和操作获得，即 sum(x2, y2) - sum(x2, y1 - 1) - sum(x1 - 1, y2) + sum(x1 - 1, y1 - 1)。 （利用容斥原理的基本思想）
</code></pre><p>add(x, y, v)和sum(x, y)可以利用二维树状数组实现，二维树状数组可以理解成每个C结点上又是一棵树状数组（可以从二维数组的概念去理解，即数组的每个元素都是一个数组），具体代码如下：</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">add</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> y,<span class="keyword">int</span> v)</span></span>&#123;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i = x; i &lt;= n; i += lowbit(i))&#123;</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> j = y; j &lt;= n; j += lowbit(j))&#123; </span><br><span class="line">            c[i][j]+= v;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">sum</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> y)</span></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> s =<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i = x; i ; i -= lowbit(i))&#123;</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> j = y; j ; j -= lowbit(j))&#123; </span><br><span class="line">            s += c[i][j];</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> s;</span><br><span class="line"> &#125;</span><br></pre></td></tr></table></figure>
<h2 id="练习题目"><a href="#练习题目" class="headerlink" title="练习题目"></a>练习题目</h2><h3 id="岩殿居蟹"><a href="#岩殿居蟹" class="headerlink" title="岩殿居蟹"></a><a href="https://scut.online/contest/39/B" target="_blank" rel="noopener">岩殿居蟹</a></h3><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;cstdio&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> N=<span class="number">100005</span>;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">long</span> <span class="keyword">long</span> M=<span class="number">1000000007l</span>l;</span><br><span class="line"><span class="keyword">long</span> <span class="keyword">long</span> n,a[N],b[N];</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">lowbit</span><span class="params">(<span class="keyword">int</span> x)</span></span>&#123;</span><br><span class="line">	<span class="keyword">return</span> x&amp;(-x);</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">add</span><span class="params">(<span class="keyword">long</span> <span class="keyword">long</span> *arr,<span class="keyword">int</span> x,<span class="keyword">int</span> v)</span></span>&#123;</span><br><span class="line">	<span class="keyword">while</span>(x&lt;=n)&#123;</span><br><span class="line">		arr[x]+=v;</span><br><span class="line">		x+=lowbit(x);</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">long</span> <span class="keyword">long</span> <span class="title">sum</span><span class="params">(<span class="keyword">long</span> <span class="keyword">long</span> *arr,<span class="keyword">int</span> x)</span></span>&#123;</span><br><span class="line">	<span class="keyword">long</span> <span class="keyword">long</span> ans=<span class="number">0</span>;</span><br><span class="line">	<span class="keyword">while</span>(x&gt;<span class="number">0</span>)&#123;</span><br><span class="line">		ans+=arr[x];</span><br><span class="line">		<span class="keyword">while</span>(ans&gt;=M)ans-=M;</span><br><span class="line">		<span class="comment">//ans%=M;</span></span><br><span class="line">		x-=lowbit(x);</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> ans;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">	<span class="comment">//freopen("input.txt","r",stdin);</span></span><br><span class="line">	<span class="comment">//freopen("answer.txt","w",stdout);</span></span><br><span class="line">	<span class="comment">//cin&gt;&gt;n;</span></span><br><span class="line">	<span class="built_in">scanf</span>(<span class="string">"%lld"</span>,&amp;n);</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++)&#123;</span><br><span class="line">		<span class="keyword">int</span> x;</span><br><span class="line">		<span class="comment">//cin&gt;&gt;x;</span></span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">"%d"</span>,&amp;x);</span><br><span class="line">		add(a,i,x);</span><br><span class="line">		add(b,i,i*x);</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="comment">/*for(int i=1;i&lt;=n;i++)&#123;</span></span><br><span class="line"><span class="comment">		printf("a[%d]=%lld,b[%d]=%lld\n",i,sum(a,i)-sum(a,i-1),i,sum(b,i)-sum(b,i-1));</span></span><br><span class="line"><span class="comment">	&#125;*/</span></span><br><span class="line">	<span class="keyword">int</span> m;</span><br><span class="line">	<span class="built_in">cin</span>&gt;&gt;m;</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=m;i++)&#123;</span><br><span class="line">		<span class="keyword">char</span> s;</span><br><span class="line">		<span class="keyword">int</span> x,y;</span><br><span class="line">		<span class="comment">//cin.get();</span></span><br><span class="line">		<span class="comment">//cin&gt;&gt;s&gt;&gt;x&gt;&gt;y;</span></span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">" %c%d%d"</span>,&amp;s,&amp;x,&amp;y);</span><br><span class="line">		<span class="keyword">if</span>(s==<span class="string">'C'</span>)&#123;</span><br><span class="line">			<span class="keyword">int</span> temp=sum(a,x)-sum(a,x<span class="number">-1</span>);</span><br><span class="line">			add(a,x,-temp+y);</span><br><span class="line">			add(b,x,-x*temp+x*y);</span><br><span class="line">		&#125;<span class="keyword">else</span> <span class="keyword">if</span>(s==<span class="string">'Q'</span>)&#123;</span><br><span class="line">			<span class="keyword">long</span> <span class="keyword">long</span> ans=sum(b,y)-sum(b,x<span class="number">-1</span>)-((x<span class="number">-1</span>)*sum(a,y))+((x<span class="number">-1</span>)*sum(a,x<span class="number">-1</span>));</span><br><span class="line">			<span class="keyword">while</span>(ans&lt;<span class="number">0</span>)ans+=M;</span><br><span class="line">			<span class="keyword">while</span>(ans&gt;=M)ans-=M;</span><br><span class="line">			<span class="comment">//cout&lt;&lt;ans&lt;&lt;endl;</span></span><br><span class="line">			<span class="built_in">printf</span>(<span class="string">"%lld\n"</span>,ans);</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="comment">/*printf("after i=%d\n",i);</span></span><br><span class="line"><span class="comment">		for(int i=1;i&lt;=n;i++)&#123;</span></span><br><span class="line"><span class="comment">			printf("a[%d]=%lld,b[%d]=%lld\n",i,sum(a,i)-sum(a,i-1),i,sum(b,i)-sum(b,i-1));</span></span><br><span class="line"><span class="comment">		&#125;*/</span></span><br><span class="line">	&#125;</span><br><span class="line">	</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="待补充内容"><a href="#待补充内容" class="headerlink" title="待补充内容"></a>待补充内容</h2><p>树状数组求区间最值</p>
<h2 id="参考博文链接"><a href="#参考博文链接" class="headerlink" title="参考博文链接"></a>参考博文链接</h2><p><a href="https://www.cnblogs.com/George1994/p/7710886.html" target="_blank" rel="noopener">树状数组的原理和实现</a><br><a href="https://www.cnblogs.com/circlegg/p/7189676.html" target="_blank" rel="noopener">树状数组lowbit()函数原理的解释 x&amp;(x^(x-1)) x&amp;-x</a><br><a href="https://www.cnblogs.com/lulizhiTopCoder/p/8384784.html" target="_blank" rel="noopener">前缀和与差分</a><br><a href="https://baijiahao.baidu.com/s?id=1608134336919624510&amp;wfr=spider&amp;for=pc" target="_blank" rel="noopener">洛谷日报第22期可以代替线段树的树状数组？</a><br><a href="http://www.cppblog.com/menjitianya/archive/2015/11/02/212171.html" target="_blank" rel="noopener">夜深人静写算法（三） - 树状数组</a><br><a href="https://www.cnblogs.com/xiongmao-cpp/p/5043340.html" target="_blank" rel="noopener">算法学习（二）——树状数组求逆序数</a></p>

      
    </div>
    <footer class="article-footer">
      <a data-url="http://yoursite.com/2018/12/08/树状数组/" data-id="cjpevtebu00039gtkvefy9uni" class="article-share-link">Share</a>
      
      
    </footer>
  </div>
  
    
<nav id="article-nav">
  
    <a href="/2018/12/08/线段树/" id="article-nav-newer" class="article-nav-link-wrap">
      <strong class="article-nav-caption">Newer</strong>
      <div class="article-nav-title">
        
          线段树
        
      </div>
    </a>
  
  
    <a href="/2018/12/08/hello/" id="article-nav-older" class="article-nav-link-wrap">
      <strong class="article-nav-caption">Older</strong>
      <div class="article-nav-title">hello</div>
    </a>
  
</nav>

  
</article>

</section>
        
          <aside id="sidebar">
  
    

  
    

  
    
  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Archives</h3>
    <div class="widget">
      <ul class="archive-list"><li class="archive-list-item"><a class="archive-list-link" href="/archives/2018/12/">December 2018</a></li></ul>
    </div>
  </div>


  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Recent Posts</h3>
    <div class="widget">
      <ul>
        
          <li>
            <a href="/2018/12/08/线段树/">线段树</a>
          </li>
        
          <li>
            <a href="/2018/12/08/树状数组/">(no title)</a>
          </li>
        
          <li>
            <a href="/2018/12/08/hello/">hello</a>
          </li>
        
          <li>
            <a href="/2018/12/07/hello-world/">Hello World</a>
          </li>
        
      </ul>
    </div>
  </div>

  
</aside>
        
      </div>
      <footer id="footer">
  
  <div class="outer">
    <div id="footer-info" class="inner">
      &copy; 2018 John Doe<br>
      Powered by <a href="http://hexo.io/" target="_blank">Hexo</a>
    </div>
  </div>
</footer>
    </div>
    <nav id="mobile-nav">
  
    <a href="/" class="mobile-nav-link">Home</a>
  
    <a href="/archives" class="mobile-nav-link">Archives</a>
  
</nav>
    

<script src="//ajax.googleapis.com/ajax/libs/jquery/2.0.3/jquery.min.js"></script>


  <link rel="stylesheet" href="/fancybox/jquery.fancybox.css">
  <script src="/fancybox/jquery.fancybox.pack.js"></script>


<script src="/js/script.js"></script>



  </div>
</body>
</html>